package leetcode;

public class SplitArrayLargestSum {

	// binary search
	// The answer is between maximum value of input array numbers and sum of
	// those numbers.
	// low = maximum, right = sum(array)
	// binary search, and judge if middle is valid

	// The lower bound of low can be sum/m , so it speeds up a bit.
	public int splitArray(int[] nums, int m) {
		if (nums == null || nums.length <= 0) {
			return 0;
		}
		int max = Integer.MIN_VALUE;
		int sum = 0;
		for (int i = 0; i < nums.length; i++) {
			max = Math.max(max, nums[i]);
			sum += nums[i];
		}
		int low = max;
		int high = sum;
		int middle = 0;
		while (low < high) {
			middle = low + (high - low) / 2;
			// 如果能够满足条件,说明middle还有下降的可能
			if (isValid(nums, m, middle)) {
				high = middle;
			} else {
				low = middle + 1;
			}
		}
		return low;
	}

	// 判断将arr分成m份，所有子数组中最大值是否会小于等于max
	public boolean isValid(int[] arr, int m, int max) {
		int count = 1;
		int curSum = 0;
		for (int num : arr) {
			curSum += num;
			if (curSum > max) {
				// 注意这里的，curSum要赋值为num，表示前面的数为一份
				curSum = num;
				count++;
				if (count > m) {
					return false;
				}
			}
		}
		return true;
	}
}
